package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月12日
*时间：下午5:34:29
*/
public class Q52 {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public int[] nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int index = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                index = i - 1;
                break;
            }
        }
        int swap = 0;
        for (int i = nums.length - 1; i > index; i--) {
            if (nums[i] > nums[index]) {
                swap = i;
                break;
            }
        }
        swap(nums, index, swap);
        if (index == swap && swap == 0) {
            reverse(nums, index, nums.length - 1);
        } else {
            reverse(nums, index + 1, nums.length - 1);
        }
        return nums;
    }

    private void reverse(int[] nums, int index, int i) {
        while (index < i) {
            swap(nums, index, i);
            index++;
            i--;
        }

    }

    private void swap(int[] nums, int index, int swap) {
        int k = nums[index];
        nums[index] = nums[swap];
        nums[swap] = k;
    }

    @Test
    public void testA() {
        int[] nums = { 2, 1, 1 };
        int rs[] = nextPermutation(nums);
        for (int i : rs) {
            System.out.print(i);
        }
    }
}
